package com.fenyin.samples.study.jdk.datastruct.list;  

/**
 * 双向链表 
 *@Author:fengzhichao  
 *@Since:2012-12-26  
 *@Version:1.1.0
 */
public class DoubleLinkedList<V> {
	
	//头节点
	private Entry<V> head;
	
	//链表长度
	private int size;
	
	public DoubleLinkedList(){
		this.head = new Entry<V>(null);
		this.size = 0;
	}
	
	/**
	 * 表头插入元素
	 * 最坏时间复杂度=最好时间复杂度=O(1)
	 */
	public void addFirst(V e){
		Entry<V> entry = new Entry<V>(e);
		if(head.next == null){//判断是否为空表
			head.next = entry;//头向后指向entry
			entry.pret= head;//entry向前指向head
			size++;
		}else{//否则
			head.next.pret=entry;//entry与后节点建立关系
			entry.next = head.next;
			
			head.next = entry;//entry与头节点建立关系
			entry.pret=head;
			size++;
		}
	}
	
	/**
	 * 表尾插入元素
	 * 最坏时间复杂度=O(n)
	 * 最好时间复杂度=O(1)
	 */
	public void addLast(V e){
		Entry<V> entry = new Entry<V>(e);
		Entry<V> p = head;
		for(; p.next!=null;){//移动到最后一个节点
			p = p.next;
		}
		p.next = entry;
		entry.pret=p;
		size++;
	}
	
	/**
	 * 表头删除元素
	 * 最坏时间复杂度=最好时间复杂度=O(1)
	 */
	public void removeFirst(){
		if(head.next == null){//如果是空表
			return ;
		}
		Entry<V> first = head.next;//被删除的节点
		if(first.next!=null){
			first.next.pret = head;
		}
		head.next = first.next;
		size--;
	}
	
	/**
	 * 表尾删除元素
	 * 最坏时间复杂度=O(n)
	 * 最好时间复杂度=O(1)
	 */
	public void removeLast(){
		if(head.next == null){//如果是空表
			return ;
		}
		Entry<V> p = head;
		for(; p.next.next!=null;){//移动到倒数第二个节点
			p = p.next;
		}
		p.next = null;
		size--;
	}
	
	/**
	 * 获取指定位置的元素
	 * 最坏时间复杂度=O(n)
	 * 最好时间复杂度=O(1)
	 */
	public V get(int i){
		if(i > size()-1 || i <0){
			throw new IndexOutOfBoundsException("链表越界");
		}
		Entry<V> curreny = head.next;
		for(int n =0; n < this.size; n++){
			if(n == i){
				return curreny.value;
			}else{
				curreny = curreny.next;
			}
		}
		return null;
	}
	
	public int size(){
		return this.size;
	}
	
	static class Entry<V>{
		//数据域
		V value;
		//指针域
		Entry pret;//反向链表
		Entry next;//正向链表
		
		public Entry(V value){
			this.value = value;
		}
	}
	
}
